package com.gitee.wsl.mathematics.geometry.d3.utils

import com.gitee.wsl.mathematics.vector.ext.directionTo
import com.gitee.wsl.mathematics.vector.ext.dot
import com.gitee.wsl.mathematics.vector.vec3.Vec3



/** Class containing utilities and algorithms intended to be internal to the library.
 * Absolutely no guarantees are made regarding the stability of this API.
 */
object EuclideanUtils {
    /** Number of vertices in a triangle, i.e. `3`.  */
    const val TRIANGLE_VERTEX_COUNT: Int = 3

    /** Convert a convex polygon defined by a list of vertices into a triangle fan. The vertex forming the largest
     * interior angle in the polygon is selected as the base of the triangle fan. Callers are responsible for
     * ensuring that the given list of vertices define a geometrically valid convex polygon; no validation (except
     * for a check on the minimum number of vertices) is performed.
     * @param <T> triangle result type
     * @param vertices vertices defining a convex polygon
     * @param fn function accepting the vertices of each triangle as a list and returning the object used
     * to represent that triangle in the result; each argument to this function is guaranteed to
     * contain 3 vertices
     * @return a list containing the return results of the function when passed the vertices for each
     * triangle in order
     * @throws IllegalArgumentException if fewer than 3 vertices are given
    </T> */
    fun <T> convexPolygonToTriangleFan(
        vertices: List<Vec3>,
        fn: (List<Vec3>)->T,
    ): List<T> {
        val size = vertices.size
        require(size >= TRIANGLE_VERTEX_COUNT) {
            "Cannot create triangle fan: " + TRIANGLE_VERTEX_COUNT +
                    " or more vertices are required but found only " + vertices.size
        }
        if (size == TRIANGLE_VERTEX_COUNT) {
            return listOf(fn(vertices))
        }

        val triangles: MutableList<T> = ArrayList<T>(size - 2)

        val fanIdx = findBestTriangleFanIndex(vertices)
        var vertexIdx = (fanIdx + 1) % size

        val fanBase = vertices[fanIdx]
        var vertexA = vertices[vertexIdx]
        var vertexB: Vec3

        vertexIdx = (vertexIdx + 1) % size
        while (vertexIdx != fanIdx) {
            vertexB = vertices[vertexIdx]

            triangles.add(fn(listOf(fanBase, vertexA, vertexB)))

            vertexA = vertexB
            vertexIdx = (vertexIdx + 1) % size
        }

        return triangles
    }

    /** Find the index of the best vertex to use as the base for a triangle fan split of the convex polygon
     * defined by the given vertices. The best vertex is the one that forms the largest interior angle in the
     * polygon since a split at that point will help prevent the creation of very thin triangles.
     * @param vertices vertices defining the convex polygon; must not be empty; no validation is performed
     * to ensure that the vertices actually define a convex polygon
     * @return the index of the best vertex to use as the base for a triangle fan split of the convex polygon
     */
    private fun findBestTriangleFanIndex(vertices: List<Vec3>): Int {
        val it = vertices.iterator()

        var curPt = it.next()
        var nextPt: Vec3

        val lastVec: Vec3 = vertices[vertices.size - 1].directionTo(curPt)
        var incomingVec = lastVec
        var outgoingVec: Vec3

        var bestIdx = 0
        var bestDot = -1.0

        var idx = 0
        var dot: Double
        while (it.hasNext()) {
            nextPt = it.next()
            outgoingVec = curPt.directionTo(nextPt)

            dot = incomingVec.dot(outgoingVec)
            if (dot > bestDot) {
                bestIdx = idx
                bestDot = dot
            }

            curPt = nextPt
            incomingVec = outgoingVec

            ++idx
        }

        // handle the last vertex on its own
        dot = incomingVec.dot(lastVec)
        if (dot > bestDot) {
            bestIdx = idx
        }

        return bestIdx
    }
}
